
/**
 * 两数之和
 * 升序排列的有序数组
 * 输⼊: numbers = [2, 7, 11, 15], target = 9
 * 输出: [1,2]
 * 解释: 2 与 7 之和等于⽬标数 9 。因此 index1 = 1, index2 = 2 。
 */
public class TwoSum {

    /**
     * 对撞指针
     */
    public int[] solution3(int[] arr, int target) {
        int n = arr.length;
        if (n < 2) {
            throw new IllegalArgumentException("len of arr is illegal!");
        }

        int l = 0, r = n - 1;
        while ( l < r) {
            if (arr[l] + arr[r] == target) {
                int [] res = {l + 1, r + 1};
                return res;
            } else if (arr[l] + arr[r] < target) {
                l ++;
            } else {
                r --;
            }
        }

        throw new IllegalArgumentException("no target!");
    }

    /**
     * 循环+二分查找
     */
    public int[] solution2(int[] arr, int target) {
        int n = arr.length;
        if (n < 2) {
            throw new IllegalArgumentException("len of arr is illegal!");
        }

        for (int i = 0; i < n; i++) {
            int j = binarySearch(arr, i + 1, n -1, target - arr[i]);
            if (j != -1) {
                int[] res = {i + 1, j + 1};
                return res;
            }
        }

        throw new IllegalArgumentException("no target!");
    }

    private int binarySearch(int[] arr, int l, int r, int target) {
        int n = arr.length;
        if (l < 0 || l > n - 1) {
            throw new IllegalArgumentException("l is illegal!");
        }

        if (r < 0 || r > n - 1) {
            throw new IllegalArgumentException("r is illegal!");
        }

        while (l <= r) {
            int m = l + (r - 1) / 2;
            if (arr[m] == target) {
                return m;
            } else if (arr[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }

    public int[] solution(int[] arr, int target) {
        int n = arr.length;
        if (n < 2) {
            throw new IllegalArgumentException("length of arr is illegal");
        }

        for (int i = 0; i < n; i++) {
            for (int j = i +1; j < n; j++) {
                if (arr[i] + arr[j] == target) {
                    int[] res = {i + 1, j + 1};
                    return res;
                }
            }
        }

        throw new IllegalArgumentException("no target!");
    }

    public static void main(String[] args) {
        int[] arr = {2, 7, 11, 15};
        System.out.println(Arrays.toString(new TowSum().solution(arr, 9)));
    }
}